package com.sjf.day03.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 图
 *
 * @author <huangtang>
 * @since 2022/1/13 15:00
 **/
public class Graph {

    List<String> vertexList; //存储顶点集合
    int[][] edges; //存储图对应的邻接矩阵
    int numOfEdges; //边的个数
    boolean[] isVisited;//某个顶点是否被访问

    public static void main(String[] args) {
        String[] VertexValue = {"1", "2", "3", "4", "5", "6", "7", "8"};
        //String[] VertexValue = {"A", "B", "C", "D", "E"};
        int n = VertexValue.length; //节点个数
        Graph graph = new Graph(n); //创建图对象
        for (String s : VertexValue) {
            graph.insertVertex(s); //插入顶点到图中
        }
        /*
        graph.insertEdges(0, 1, 1);//A-B
        graph.insertEdges(0, 2, 1);
        graph.insertEdges(1, 2, 1);
        graph.insertEdges(1, 3, 1);
        graph.insertEdges(1, 4, 1);*/
        /* 添加边 */

        graph.insertEdges(0, 1, 1);//1-2
        graph.insertEdges(0, 2, 1);//1-3
        graph.insertEdges(1, 3, 1);//1-4
        graph.insertEdges(1, 4, 1);//2-5
        graph.insertEdges(2, 5, 1);//2-5
        graph.insertEdges(2, 6, 1);//2-5
        graph.insertEdges(3, 7, 1);//3-5
        graph.insertEdges(4, 5, 1);//4-6
        graph.insertEdges(5, 6, 1);//4-6

        System.out.println("遍历图");
        graph.show();

        /*  测试dfs */
        System.out.println("深度遍历");
        graph.dfs();

        graph.reset(); //重置访问数组

        /* 测试bfs */
        System.out.println("\n广度遍历");
        graph.bfs();
    }

    public void reset() {
        Arrays.fill(isVisited, false);
    }

    /**
     * 初始化图
     */
    public Graph(int n) {
        edges = new int[n][n];
        isVisited = new boolean[n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0; //默认为0，还未建立连接
    }

    /**
     * 插入顶点
     * @param vertex 需要插入的顶点
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 无向图的添加边
     * @param v1 第一个顶点
     * @param v2 第二个顶点
     * @param weight 权重 (0 未连接，1 连接）
     */
    public void insertEdges(int v1, int v2, int weight){
        edges[v1][v2] = weight; //无向图 需要双向连接
        edges[v2][v1] = weight;
        numOfEdges++; //边数+1
    }

    /* 图中常用方法*/

    /**
     * 得到传入索引节点的第一个邻接节点
     *
     * @param index 传入节点索引
     * @return -1 表示没有邻接节点
     * 否则返回邻接节点索引
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if(edges[index][i] == 1){ //while equal 1 return i (is index)
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标获取下一个邻接节点
     *
     * @param v1 前一个节点
     * @param v2 当前节点
     * @return 下一个邻接节点索引
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 遍历所有节点，进行bfs
     */
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    /**
     * 广度优先算法 bfs
     *
     * @param isVisited 判断节点是否被访问过的数组
     * @param index     当前访问节点的索引
     */
    private void bfs(boolean[] isVisited, int index) {
        int u;//表示队列头节点的下标
        int w;//邻接节点w
        //队列，存放以头节点开始的遍历节点顺序
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.print(getValueByIndex(index) + "->"); //访问该节点
        isVisited[index] = true;//标记该节点为已访问
        queue.addLast(index); //将访问过的节点加入到队列尾部

        while (!queue.isEmpty()) {
            //取出头节点的下标
            u = queue.removeFirst();
            w = getFirstNeighbor(u); //得到邻接节点的下标
            while (w != -1) { //找到邻接节点
                if (!isVisited[w]) { //判断是否访问过       index
                    System.out.print(getValueByIndex(w) + "->");
                    isVisited[w] = true;//标记访问
                    queue.addLast(w); //入队列
                }
                //以u为节点找w后面的下一个邻接节点
                w = getNextNeighbor(u, w);
            }
        }
    }

    /**
     * 深度优先算法 dfs
     *
     * @param isVisited 判断是否访问数组
     * @param index     索引
     */
    private void dfs(boolean[] isVisited, int index) {
        //首先访问该节点，并输出
        System.out.print(getValueByIndex(index) + "->");
        isVisited[index] = true; //将该节点置为已经访问
        int i = getFirstNeighbor(index); //查找节点index的第一个邻接节点i
        while (i != -1) { //说明有邻接节点
            if (!isVisited[i]) { //判断是否访问过
                dfs(isVisited, i); //对下一个邻接节点进行dfs
            }
            //如果i被访问过,回溯到上一个节点
            i = getNextNeighbor(index, i);
        }
    }

    /**
     * 对上面dfs进行重载，遍历所有节点，进行dfs
     */
    public void dfs(){
        //遍历所有的节点
        for (int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

    /**
     * 获取图中顶点个数
     * @return int 顶点个数
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

    /**
     * 获取图中边的个数
     * @return int 边的个数
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }

    /**
     * 获取对应索引的顶点
     * @param index 索引
     * @return 返回顶点
     */
    public String getValueByIndex(int index){
        return vertexList.get(index);
    }

    /**
     * 返回两个顶点的权值
     * @param v1 第一个顶点
     * @param v2 第二个顶点
     * @return 返回权值
     */
    public int getWeight(int v1, int v2){
        return edges[v1][v2];
    }

    /**
     * 打印图
     */
    public void show(){
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }

}


